class Solution:
    def numberOfWays(self, s: str, t: str, k: int) -> int:
        # python版的实现, 避免了中间结果会溢出的问题

        n = len(s)
        s *= 2
        pos0 = s.find(t)
        if pos0 == -1:
            return 0
        pos1 = s.find(t, pos0 + 1)

        mod = 10**9 + 7
        nmod = n * mod

        nm1 = n - 1
        k0 = k
        p = 1
        while k0:
            if k0 & 1:
                p = p * nm1 % nmod
            nm1 = nm1 * nm1 % nmod
            k0 >>= 1

        sign = -1 if k & 1 else 1

        p0 = (p + sign * (n - 1)) % nmod // n % mod
        p1 = (p - sign) % nmod // n % mod

        result = 0
        r = [pos0] if pos1 == -1 else range(pos0, n, pos1 - pos0)
        for pos in r:
            result += p0 if pos == 0 else p1
            result %= mod
        return result
